#include <iostream>

#define Size 10

class MinHeap
{
public:
    MinHeap():len(0){}
    
    void Insert(int value)
    {
        array[len++] = value;
        SiftUp(len-1);
    }

    void RemoveRoot()
    {   
        if(len == 0)
            return;
        array[0] = array[len-1];
        SiftDown(0);
        len--;

    }

    int* Search(int value)
    {
        for(int i = 0; i < len;i++)
        {
            if(array[i] == value)
            {
                return &array[i];
            }
        }
        return nullptr;
    }

    int GetMin()
    {
        return array[0];
    }
    void show()
    {
        for(int i = 0; i < len;i++)
        {
            std::cout<<array[i]<<" ";
        }
        std::cout<<std::endl;
    }
private:
    int GetParent(int i){return ( i -1)/2;}
    int GetLeftChild(int i){return 2* i + 1;}
    int GetRightChild(int i){return 2*i + 2;}

    //上浮操作
    void SiftUp(int i)
    {   
        while(i > 0&&array[i] <  array[GetParent(i)])
        {
            std::swap(array[i],array[GetParent(i)]);
            i = GetParent(i);
        }
    }
    //下沉操作
    void SiftDown(int i)
    {
        int leftChild = GetLeftChild(i);
        int rightChild = GetRightChild(i);

        int MinIndex = i;
        if(leftChild < len && array[leftChild] < array[i])
        {
            MinIndex = leftChild;
        }

        if(rightChild < len&& array[rightChild] < array[MinIndex])
        {
            MinIndex = rightChild;
        }
        if(MinIndex != i)
        {
            std::swap(array[i],array[MinIndex]);
            SiftDown(MinIndex);
        }
    }
    int array[Size];
    int len;
};

int main()
{   
    int a[10] = {5,2,1,6,2,9,10,8,4,12};
    MinHeap heap;
    // for(int i = 0;i < 6;i++)
    //     heap.Insert(i+1);
    // heap.RemoveRoot();
    // heap.show();
    for(int i = 0; i < 10;i++)
    {
        if(i < 5)
        {
            heap.Insert(a[i]);
        }
        else
        {
            if(heap.GetMin() < a[i])
            {
                heap.RemoveRoot();
                heap.Insert(a[i]);
            }
        }
    }
    heap.show();
    return 0;
}